package com.itheima.leetcode.od.b.backtracking;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * 小明有n个可选运动，每个运动有对应卡路里，想选出其中k个运动且卡路里和为t。k，t，n都是给定的。求出可行解数量
 * <p>
 * 输入描述
 * <p>
 * 第一行输入n t k
 * 第二行输入 每个运动的卡路里 按照空格进行分割
 * 备注
 * 0<n<10
 * t>0，0<k<=n
 * 每个运动量的卡路里>0
 * <p>
 * 输出描述
 * <p>
 * 求出可行解数量
 * <p>
 * 示例1：
 * <p>
 * 输入
 * <p>
 * 4 3 2
 * 1 1 2 3
 * <p>
 * 输出
 * <p>
 * 2
 * <p>
 * 说明
 * 可行解为2，选取{0,2},{1,2}两种方式。
 * <p>
 * 思路
 * <p>
 * 1. 问题分析
 * <p>
 * 1.1 题目理解
 * <p>
 * 输入内容的详细解释：
 * <p>
 * 第一行包含三个整数：n（运动总数）、t（目标卡路里和）、k（需要选择的运动数量）
 * 第二行包含n个整数，表示每个运动的卡路里值，以空格分隔
 * 输出要求的具体说明：
 * <p>
 * 输出一个整数，表示满足条件的组合数量
 * 条件：从n个运动中选择k个，使得这k个运动的卡路里和等于t
 * 约束条件的整理：
 * <p>
 * 0 < n < 10（运动总数小于10）
 * t > 0（目标卡路里和为正数）
 * 0 < k <= n（选择的运动数量大于0且不超过总运动数）
 * 每个运动的卡路里值均为正数
 * <p>
 * 1.2 问题建模
 * <p>
 * 将问题转化为具体的数据结构：
 * <p>
 * 输入的运动卡路里可以用数组表示
 * 本质是一个组合问题，需要从n个数中选择k个数，使其和为t
 * 确定需要使用的算法类型：
 * <p>
 * 这是一个组合计数问题
 * 可以使用回溯法（DFS）或动态规划来解决
 * 分析问题的数学模型：
 * <p>
 * 组合数学中的子集选择问题
 * 需要满足两个条件：
 * 选择恰好k个元素
 * 这k个元素的和恰好为t
 * <p>
 * 2. 解题思路
 * <p>
 * 2.1 算法选择
 * <p>
 * 最优算法：
 * <p>
 * 使用回溯法（DFS）
 * 原因：问题规模较小（n<10），回溯法的性能足够好，且实现直观
 * 时间和空间复杂度分析：
 * <p>
 * 时间复杂度：O(C(n,k))，其中C(n,k)是组合数
 * 空间复杂度：O(k)，递归栈的深度
 * 2.2 核心数据结构
 * 主要数据结构的选择理由：
 * <p>
 * 使用数组存储输入的卡路里值
 * 使用递归函数的参数来追踪当前状态
 * 数据结构的具体实现方式：
 * <p>
 * 一维数组存储卡路里值
 * 递归函数参数包含：当前位置、已选数量、当前和
 * 数据结构的操作复杂度：
 * <p>
 * 数组访问：O(1)
 * 递归调用：每层复杂度O(1)
 * <p>
 * 2.3 关键算法步骤
 * <p>
 * 算法的详细步骤说明：
 * <p>
 * 读取输入参数n、t、k和卡路里数组
 * 实现DFS函数，包含以下参数：
 * 当前考虑的位置
 * 已经选择的运动数量
 * 当前卡路里和
 * DFS过程中：
 * 对当前位置的运动进行选择或不选择
 * 记录满足条件的解的数量
 * 每个步骤的作用和原理：
 * <p>
 * 选择当前运动：更新已选数量和卡路里和
 * 不选择当前运动：直接考虑下一个运动
 * 递归终止条件：已选够k个运动或达到数组末尾
 * ————————————————
 */
public class Slimming {
    public static void main(String[] args) {
        /*Scanner scanner = new Scanner(System.in);
        // 读取输入
        int n = scanner.nextInt();
        int t = scanner.nextInt();
        int k = scanner.nextInt();

        int[] calories = new int[n];
        for (int i = 0; i < n; i++) {
            calories[i] = scanner.nextInt();
        }*/

        // 读取输入
        int[] params = Arrays.stream("4 3 2".split(" ")).mapToInt(Integer::parseInt).toArray();
        int n = params[0];
        int t = params[1];
        int k = params[2];

        int[] calories = Arrays.stream("1 1 2 3".split(" ")).mapToInt(Integer::parseInt).toArray();

        // 输出结果
        System.out.println(dfs(0, k, t, calories, new LinkedList<>()));
    }

    /**
     * 深度优先搜索辅助函数
     *
     * @param start    当前考虑的运动索引
     * @param k        还需要选择的运动数量
     * @param t        目标卡路里和
     * @param calories 卡路里数组
     * @return 满足条件的组合数量
     */
    private static int dfs(int start, int k, int t, int[] calories, LinkedList<Integer> stack) {
        // 基础情况：已经选够k个运动
        if (0 == t && k == stack.size()) {
            return 1;
        }

        int count = 0;

        for (int i = start; i < calories.length; i++) {
            if (t < calories[i]) {
                continue;
            }
            if (k == stack.size()) {
                continue;
            }
            if (k - stack.size() > calories.length - start + 1) {
                continue;
            }
            stack.push(i);
            count += dfs(i + 1, k, t - calories[i], calories, stack);
            stack.pop();
        }

        return count;
    }
}